#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class Solution{
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());  // 将输入数组排序，方便后面使用双指针法查找，如果不排序，在查找剩下两个数时需要遍历整个数组，时间复杂度会很高
        vector<vector<int>> result;  // 存储符合条件的三元组
        int n = nums.size();
        for (int i = 0; i < n - 2; i++) {  // 枚举第一个数，范围是 0 到 n-3
            if (i > 0 && nums[i] == nums[i-1]) 
                continue;  // 避免重复，如果当前数和上一个数的第一个数相同，跳过
            int target = -nums[i];  // 计算目标值，为了让三个数的和等于 0，要让剩下两个数的和等于 -nums[i]
            int j = i + 1, k = n - 1;  // 双指针法找出剩下两个数，左指针 j 初始值为 i+1，右指针 k 初始值为 n-1
            while (j < k) {
                int sum = nums[j] + nums[k];  // 计算两个数的和
                if (sum == target) {  // 找到一个符合条件的三元组
                    result.push_back({nums[i], nums[j], nums[k]}); // 将三个数组成的向量加入结果数组中
                    j++;
                    k--;  // 移动双指针
                    while (j < k && nums[j] == nums[j - 1]) 
                        j++;  // 避免重复，如果左指针移动后的数和前一个数相同，继续移动左指针
                    while (j < k && nums[k] == nums[k + 1]) 
                        k--;  // 避免重复，如果右指针移动后的数和后一个数相同，继续移动右指针
                } 
                else if (sum < target) {  // 和小于目标值，移动左指针，以增大两数之和
                    j++;
                } 
                else {  // 和大于目标值，移动右指针，以减小两数之和
                    k--;
                }
            }
        }
        return result;  // 返回结果数组
    }
};

int main() {
    Solution s;
    vector<int> nums = {-2,0,1,1,2}; 
    vector<vector<int>> result = s.threeSum(nums);
    for (auto& vec : result) {  
        cout << "[";  
        for (int i = 0; i < vec.size(); i++) {  // 遍历当前向量
            cout << vec[i];  // 输出当前数值
            if (i != vec.size() - 1) cout << ", ";  // 如果不是最后一个数，输出逗号和空格
        }
        cout << "]" << endl; 
    }
    return 0; 
}